package labuladong.动态规划;

public class 最长公共子序列 {

    public static int longestCommonStr(String s1, String s2) {
        int[][] dpArr = new int[s1.length()+1][s2.length()+1];
        return dp(s1, s2, dpArr);
    }

    public static int dp(String s1, String s2, int[][] dpArr) {
        for (int i=1; i<=s1.length(); i++) {
            for (int j=1; j<=s2.length(); j++) {
                if (s1.charAt(i-1) == s2.charAt(j-1)) {
                    dpArr[i][j] = dpArr[i-1][j-1] + 1;
                } else {
                    dpArr[i][j] = Math.max(dpArr[i-1][j], dpArr[i][j]);
                }
            }
        }
        return dpArr[s1.length()][s2.length()];
    }

    public static void main(String[] args) {
        System.out.println(longestCommonStr("abcde", "ace"));
    }
}
